package Leetcode.数组字符串;

import java.util.*;

/**
 * @Author kirito
 * @Date 2024/1/9 10:15
 * @PackageName:Leetcode.数组字符串
 * @ClassName: 字符串中的额外字符
 * @Description:
 * 给你一个下标从 0 开始的字符串 s 和一个单词字典 dictionary 。你需要将 s 分割成若干个 互不重叠 的子字符串，
 * 每个子字符串都在 dictionary 中出现过。s 中可能会有一些 额外的字符 不在任何子字符串中。
 *
 * 请你采取最优策略分割 s ，使剩下的字符 最少 。
 *
 *
 *
 * 示例 1：
 *
 * 输入：s = "leetscode", dictionary = ["leet","code","leetcode"]
 * 输出：1
 * 解释：将 s 分成两个子字符串：下标从 0 到 3 的 "leet" 和下标从 5 到 8 的 "code" 。
 * 只有 1 个字符没有使用（下标为 4），所以我们返回 1 。
 * 示例 2：
 *
 * 输入：s = "sayhelloworld", dictionary = ["hello","world"]
 * 输出：3
 * 解释：将 s 分成两个子字符串：下标从 3 到 7 的 "hello" 和下标从 8 到 12 的 "world" 。
 * 下标为 0 ，1 和 2 的字符没有使用，所以我们返回 3 。
 *
 *
 * 提示：
 *
 * 1 <= s.length <= 50
 * 1 <= dictionary.length <= 50
 * 1 <= dictionary[i].length <= 50
 * dictionary[i] 和 s 只包含小写英文字母。
 * dictionary 中的单词互不相同。
 * @Version 1.0
 */
public class 字符串中的额外字符 {
    public int minExtraChar(String s, String[] dictionary) {
        int n = s.length();       // 字符串长度
        int[] dp = new int[n+1];  // dp[i+1] 表示截至到字符串索引i位置的最少额外字符数
        // 将字典转为哈希表存储，方便查找
        Set<String> dictionarySet = new HashSet<>(Arrays.asList(dictionary));
        for(int i = 0; i < n; i++){
            dp[i + 1] = dp[i] + 1;  // 字符i不参与子串的情况
            for(int j = 0; j <= i; j++){
                // 字符i参与子串的情况，取最小值
                if(dictionarySet.contains(s.substring(j, i + 1))){
                    dp[i + 1] = Math.min(dp[i + 1], dp[j]);
                }
            }
        }
        return dp[n];   // dp[n] 即为截至到索引n-1位置的最少额外字符数
    }

}
